import java.util.*;

public class project {
    public int movingCount(int m, int n, int k) {
        if(k==0){
            return 1;
        }
        boolean[][] booleans=new boolean[m][n];
        booleans[0][0]=true;
        int ret=1;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0&&j==0||get(i)+get(j)>k){
                    continue;
                }
                if(i-1>=0){
                    booleans[i][j] |=booleans[i-1][j];
                }
                if(j-1>=0){
                    booleans[i][j] |=booleans[i][j-1];
                }
                ret+=booleans[i][j]?1:0;
            }
        }
        return ret;
    }

    private int get(int x) {
        int sum=0;
        while (x!=0){
            sum+=x%10;
            x/=10;
        }
        return sum;
    }


















    public int lenLongestFibSubseq(int[] arr) {
        Set<Integer> set=new HashSet<>();
        for(int value:arr){
            set.add(value);
        }
        int max=0;
        for(int i=0;i<arr.length;i++){
            for(int j=i+1;j<arr.length;j++){
                int x=arr[j];
                int sum=arr[i]+arr[j];
                int size=2;
                while (set.contains(sum)){
                    int y=sum;
                    sum+=x;
                    x=y;
                    size++;
                    max=Math.max(max,size);
                }
            }
        }
        return max>2?max:0;
    }















    public int maxRotateFunction(int[] nums) {
        int prev=0;
        int sum=0;
        int ret=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            prev+=i*nums[i];
        }
        ret=prev;
        for(int i=1;i<nums.length;i++){
            prev+=sum-nums.length*nums[nums.length-i];
            ret=Math.max(ret,prev);
        }
        return ret;
    }















    public int strongPasswordChecker(String password) {
        char[] ch=password.toCharArray();
        int a=0;
        int b=0;
        int c=0;
        int n=ch.length;
        for(char value:ch){
            if(value>='a'&&value<='z'){
                a=1;
            }else if(value>='0'&&value<='9'){
                b=1;
            }else if(value>='A'&&value<='Z'){
                c=1;
            }
        }
        int m=a+b+c;
        if(n<6){
            return Math.max(6-n,3-m);
        }else if(n<=20){
            int tmp=0;
            for(int i=0;i<n;){
                int j=i;
                while (j<n&&ch[j]==ch[i]){
                    j++;
                }
                int cur=j-i;
                if(cur>=3){
                    tmp+=cur/3;
                }
                i=j;
            }
            return Math.max(tmp,3-m);
        }else{
            int tmp=0;
            int[] cnts=new int[3];
            for(int i=0;i<n;){
                int j=i;
                while (j<n&&ch[j]==ch[i]){
                    j++;
                }
                int cur=j-i;
                if(cur>=3){
                    tmp+=cur/3;
                    cnts[cur%3]++;
                }
                i=j;
            }
            int base=n-20;
            int cur=base;
            for(int i=0;i<3;i++){
                if(i==2){
                    cnts[i]=tmp;
                }
                if(cnts[i]!=0&&cur!=0){
                    int t=Math.min(cnts[i]*(i+1),cur);
                    cur-=t;
                    tmp-=t/(i+1);
                }
            }
            return base+Math.max(tmp,3-m);
        }

    }
























    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> list=new ArrayList<>();
        if(n==0){
            list.add(0);
            return list;
        }
        List<List<Integer>> map=new ArrayList<>();
        for(int i=0;i<n;i++){
            map.add(new ArrayList<>());
        }
        int[] arr=new int[n];
        for(int[] edge:edges){
            arr[edge[0]]++;
            arr[edge[1]]++;
            map.get(edge[0]).add(edge[1]);
            map.get(edge[1]).add(edge[0]);
        }
        Queue<Integer> queue=new ArrayDeque<>();
        for(int i=0;i<n;i++){
            if(arr[i]==1){
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()){
            list=new ArrayList<>();
            int size=queue.size();
            for(int i=0;i<size;i++){
                int cur=queue.poll();
                list.add(cur);
                List<Integer> tmp=map.get(cur);
                for(int value:tmp){
                    arr[value]--;
                    if(arr[value]==1){
                        queue.offer(value);
                    }
                }
            }
        }
        return list;
    }
}
